package algorithms.a08MinimumSpanTrees;

import com.google.common.base.Preconditions;
import com.google.common.collect.Sets;

import java.util.Set;

/**
 * 稀疏图 - 邻接表
 *
 * @author 王昊然
 * @create 2018-02-24 15:12
 **/
public class SparseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph<Weight> {

    private int n; //节点数量
    private int m; //边的数量
    private boolean isDirected; //true有向图 false无向图
    private Set<Edge>[] g; //节点之间边的信息

    public SparseWeightedGraph(int n, boolean isDirected) {
        this.n = n;
        this.m = 0;
        this.isDirected = isDirected;
        g = new Set[n];
        for (int i = 0; i < n; i++) {
            g[i] = Sets.newHashSet();
        }
    }

    public int V() {
        return n;
    }//返回节点数

    public int E() {
        return m;
    }//返回边的个数

    public void addEdge(Edge<Weight> e) {

        assert e.V() >= 0 && e.V() < n ;
        assert e.W() >= 0 && e.W() < n ;

        // 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表
        // 我们的程序允许重边的出现

        g[e.V()].add(new Edge(e));
        if( e.V() != e.W() && !isDirected )
            g[e.W()].add(new Edge(e.W(), e.V(), e.wt()));

        m ++;
    }

    /**
     * 判断两点间是否有边
     * 不用考虑边是否有向无向，只判断v到w的情况
     *
     * @param v
     * @param w
     * @date: 2018/2/24 15:33
     * @author: 王昊然
     */
    public boolean hasEdge(int v, int w) {
        Preconditions.checkArgument(v < n && w < n, "节点值超出范围");
        return g[v].contains(w);
    }

    /**
     * 返回某一个点所有连接点的可迭代容器
     *
     * @param v
     * @date: 2018/2/26 9:38
     * @author: 王昊然
     */
    public Set<Edge> adj(int v){
        Preconditions.checkArgument(v < n, "节点值超出范围");
        return g[v];
    }

    // 显示图的信息
    public void show(){

        for( int i = 0 ; i < n ; i ++ ){
            System.out.print("vertex " + i + ":\t");
            for(Edge j : adj(i))
                System.out.print(j + "\t");
            System.out.println();
        }
    }
}
